1. Field of the Invention
2. Related Art
The present invention relates to a communications network, and in particular to the routing of packets in a network.
There is a need for high speed packet networks for use, for example, in local area networks for interconnecting computer systems, or for use as part of the internal infrastructure of a multiprocessor computer. It has been proposed to implement such networks using ultrafast photonic technology. In implementing the network, the provision of an appropriate routing mechanism for the packets has proved to be a particularly critical design problem. There are a number of potentially conflicting requirements which have to be satisfied by any routing mechanism. In particular, it is desirable that the processing overhead at each node should be kept low: otherwise, the time required to process the packet limits the throughput of the node and hence of the network. However, it is also desirable to ensure that the routing mechanism is as efficient as possible in selecting the shortest paths for packets from a source to a given destination. If the efficiency of the routing mechanism is poor, then congestion in the network rises. This again serves to limit the throughput of the network.
Many different approaches to packet routing have been proposed and studied [1-3]. By selecting a suitable network topology the decision making associated with routing can be greatly simplified. This then meets the first of the requirements identified above, by ensuring a low processing overhead. Some network topologies allow xe2x80x9cone-dimensionalxe2x80x9d routing. For example, in a uni-directional ring the source simply places a packet onto the ring and the packet eventually reaches its destination without requiring any routing decision by intermediate nodes. One-dimensional routing may also be used, for example, on buses or rings with bi-directional links. However, although one dimensional routing offers a number of attractive features, it suffers a serious limitation in that there is poor scaling of the relative routing efficiency and maximum throughput of the network as the number of nodes in the network is increased.
As an alternative to the use of one-dimensional network topologies, multi-dimensional networks may be used. The main advantage of using a multi-dimensional network, such as a two-dimensional torus network, is that there is a multiplicity of paths available between any pair of nodes on the network. It is therefore possible to adopt a routing method that selects the shortest available path, and such a method in general will have a higher relative routing efficiency and a higher value for the maximum throughput. However, existing methods of routing on multi-dimensional networks have their own serious drawbacks. Because the routing methods can select from a multiplicity of paths through the network it is possible for two or more packets to attempt to occupy the same link simultaneously. The method therefore needs to be capable of resolving the contention that arises in this case. This may be done either by using buffering within the network to store one or more of the packets until the link is free, or by deflecting one or more packets away from its optimal path, the technique known as deflection routing [1,7] Buffering can successfully maintain the packets in their correct sequence during their journey across the network. Buffering is however an unattractive solution for high-speed networks, because it introduces variable and unpredictable delay and adds to the control complexity and cost. In the case of photonic networks, there are severe technological limitations to the construction of buffers. Deflection routing does not suffer these technological limitations and is much easier to control, but deflection also causes packets to suffer variable and unpredictable delays. The packets may therefore be delivered to the destination in an incorrect sequence. A further limitation of conventional multi-dimensional networks and routing mechanisms is that it is difficult to achieve broadcasting to the nodes without using higher level transport control layers. The use of higher level transport control layers is undesirable as it introduces substantial processing delays.
The paper by Yener, B. et al., PROCEEDINGS OF THE GLOBAL TELECOMMUNICATIONS CONFERENCE (GLOBECOM), SAN FRANSISCO, NOV. 28 DEC. 2, 1994, vol. 1 of 3, IEEE, pp 169-175, and patent U.S. Pat. No. 5,297,137, discuss the use of multiple spanning trees to enhance the fault tolerance of a switch-based network. The use of two virtual rings is proposed. Each ring is embodied by an edge-disjoint spanning tree of the network and each virtual ring therefore spans every node of the network. It is therefore not possible to. route a packet efficiently simply by choosing one of the virtual rings at the outset. As a packet passes through the network, routing is carried out in a conventional fashion by making a local routing decision at intermediate nodes.
The paper by ZHENSHENG ZHANG et al, published in NETWORKING IN THE NINETIES, Bal Harbour, Apr. 7-11, 1991, vol. 3, 7 April 1991, IEEE, pp 1012-1021 discloses a network which is synchronised so that the transmissions of all the nodes begin in the start of a time slot. However, although the switching of nodes is to this extent pre-scheduled, the switching between different states is not predetermined. That is to say, it is not possible to predict in advance that a certain switch will be in a certain state at a given instant. Rather, whether or not a switch changes from one state to another in a given time slot is determined by a local routing decision made using a hot potato algorithm. The switch state therefore depends on local traffic conditions.
According to a first aspect of the present invention, there is provided a method of routing a packet in a communications network which comprises a multiplicity of nodes and links, and in which the nodes and links are configured as a multiplicity of directed trails, each directed trail linking some only of the multiplicity of nodes and the directed trails in combination spanning every node of the network, the method comprising:
a) selecting a directed trail T from the multiplicity of directed trails in dependence upon the destination of a packet, the selected trail including the source node and destination node of the packet; and
b) outputting the packet at the source node onto the selected one of the ultiplicity of directed trails.
The present invention provides a fundamentally new approach to packet routing in multi-dimensional communications networks. It potentially offers all the advantage of one-dimensional routing, whilst overcoming the crucial disadvantage of poor scalability of routing efficiency and of the maximum throughput. It also completely avoids the need for contention resolution within the network.
The invention uses a method termed by the inventor xe2x80x9cdirected trail routingxe2x80x9d. This takes advantage of the fact that a network having an appropriate topology, as further described below, can be divided into a set of distinct trails, such that no one single trail spans all of the network, but there is always one trail which leads from a given source node to a given destination node. Routing can then be carried out simply by selecting the appropriate trail linking a source node to the desired destination node. Once on the trail, the packet can be routed in a quasi-one-dimensional fashion. As in one-dimensional routing, and by contrast with the prior art approaches in the papers by Yener et al. and Zhang et al., the source node selects the entire trail from the source to the destination before sending the packet.
Preferred implementations of the invention offer the advantages of very simple processing and routing nodes which may be based on simple header-word recognition. Message delivery time is dominated by the speed of light delay. No contention is required within the network, there is no need for buffering within the network and the network is free of deadlock or livelock. Nodes in the network can be named in an arbitrary fashion. Networks embodying the present invention offer efficient routing and good throughput and these advantages are maintained as the method is scaled for larger networks. Using the invention, there is zero delay variation and packets can be delivered in the correct sequence. The invention can support both connectionless (datagram) and connection-orientated modes and in connection-orientated mode provides guaranteed bandwidth. The method also makes physical-layer broadcasting practical.
Preferably the method includes reading the destination address at each node traversed by the packet.
In preferred implementations of the invention, the only processing required at the node is that needed to determine whether or not the packet address matches the node address.
Preferably each intermediate node forwards a packet which is received at the intermediate node and which is addressed to another node in a direction which is predetermined and independent of any information carried by the packet.
An important advantage of the present invention is that it enables intermediate nodes to function without requiring any processing of the packet beyond that necessary to determine whether or not the packet destination address corresponds to the node address.
Preferably the packet is an optical packet carried on a photonic network.
Although the present invention is not limited in applicability to systems operating in the optical domain, it does offer special advantages when used with ultrafast photonic networks. It enables efficient use of the bandwidth offered by such networks, while avoiding the disadvantages of using deflection routing or the technological problems associated with the provision of optical buffers.
Preferably each directed trail in the network is a subgraph of at least one closed directed trail and consists of a directed cycle or union of a plurality of connected directed cycles from a link-disjoint directed-cycle decomposition of the network. Preferably the step of selecting a directed trail T includes synchronising the initial despatch of the packet with prescheduled switching at an intermediate node.
It is found that a particularly effective way of routing a packet along a trail formed from a number of directed cycles is to switch the optical output of the intermediate nodes at prescheduled times e.g. with a fixed periodicity, so as to connect one cycle to another cycle. The source node then determines the trail followed by the packet by outputting the packet at a time determined in relation to the switching schedule so that, at a desired node, it is switched from one cycle to the next cycle in the trail. Preferably the switching occurs at a point of connection between cycles from a link-disjoint directed-cycle decomposition of the network. Preferably the nodes switch in synchronism throughout the network between pre-scheduled pre-determined switching states. For example, in the 4xc3x974 torus network described below, a crossbar switch is associated with each node. All the crossbar switches are normally set to the cross state and repeatedly, at predetermined intervals, the crossbar switches are set to the bar state.
Although the use of temporal switching is preferred, the invention is not limited solely to such techniques. The invention might be implemented, for example, using wavelength-switching instead.
Preferably a timing sequence for the prescheduled switching of intermediate nodes comprises a frame divided into a plurality of time slots, and a source node outputs a packet onto the network in a selected one of the plurality of time slots within the timing frame, and the length of the link between successive nodes in a trail is such that a packet leaving one node in a first time slot arrives at the next successive node in a second time slot. For example, the packet may be advanced or retarded by one time slot as it passes from one node to the next.
According to a second aspect of the present invention there is provided a communications network comprising:
a) a multiplicity of nodes and links which are configured as a multiplicity of directed trails each of which spans some only of the multiplicity of nodes and the multiplicity of directed trails in combination spanning every node of the network and including at least one directed trail linking each source node and each destination node in the network;
b) means for selecting a directed trail T from the multiplicity of directed trails in dependence upon the destination of a packet; the selected trail including the source node and destination node of the packet; and
c) means for outputting the packet at the source node onto the selected one of the multiplicity of directed trails.
According to a third aspect of the present invention there is provided a communications network comprising:
a) a multiplicity of nodes and links which are configured as a multiplicity of directed trails each of which spans some only of the multiplicity of nodes and the multiplicity of directed trails in combination spanning every node of the network and including at least one directed trail linking each source node and each destination node in the network;
b) a routing controller arranged to select, in dependence upon the destination of a packet, a directed trail T from the multiplicity of directed trails, which directed trail includes the source node and destination node of the packet;
c) an input for receiving packets for transmission on the network; and
d) an output connected to the said input for receiving packets and connected to the routing controller and arranged to output a packet received at the said input onto a selected one of the said multiplicity of directed trails.
According to a fourth aspect of the present invention, there is provided an optical communications network comprising:
a) means for selecting a time slot for a packet in dependence upon the desired path for the packet through the network;
b) means for outputting the packet onto the network at a source node in the time slot selected by the means for selecting;
c) means for switching periodically the routing states of a multiplicity of routing nodes;
d) at the network nodes, means for switching the packet to different outputs according to the routing state of the respective node in the time slot in which the packet arrives at the node; and
e) means for receiving the packet at a destination node.
According to a fifth aspect of the present invention there is provided a method of routing an optical packet from a source node to a destination node in an optical communications network, comprising:
a) selecting a time slot for a packet in dependence upon the desired path for the packet through the network;
b) outputting the packet onto the network at a source node in the time slot selected in step (a);
c) switching periodically the routing states of a multiplicity of routing nodes;
d) as the packet traverses the network, at the different nodes switching the packet to different outputs according to the routing state of the respective node in the time slot in which the packet arrives at the node; and
e) receiving the packet at a destination node.
The present invention also encompasses multiprocessor computer systems, local area networks, metropolitan area networks, campus networks and communications switches using networks in accordance with the preceding aspects of the invention.